Convex Hull | Monotone Chain Algorithm

What is Convex Hull?

The convex hull of a set of points in a Euclidean space is the smallest convex polygon that encloses all of the points. In two dimensions (2D), the convex hull is a convex polygon, and in three dimensions (3D), it is a convex polyhedron....

Convex Hull | Monotone Chain Algorithm:

Monotone chain algorithm constructs the convex hull in O(n * log(n)) time. We have to sort the points first and then calculate the upper and lower hulls in O(n) time. The points will be sorted with respect to x-coordinates (with respect to y-coordinates in case of a tie in x-coordinates), we will then find the left most point and then try to rotate in clockwise direction and find the next point and then repeat the step until we reach the rightmost point and then again rotate in the clockwise direction and find the lower hull....

Quickhull Algorithm for Convex Hull:

The QuickHull algorithm is a Divide and Conquer algorithm similar to QuickSort. Let a[0…n-1] be the input array of points. Following are the steps for finding the convex hull of these points....

Complexity Analysis for Convex Hull Algorithm:

The below table enlists the time complexities of the above mentioned convex hull algorithms.where, N denotes the total number of given points....

Problems on Convex Hull:

Problem links Dynamic Convex hull | Adding Points to an Existing Convex Hull Deleting points from Convex Hull Perimeter of Convex hull for a given set of points Check if the given point lies inside given N points of a Convex Polygon Tangents between two Convex Polygons Check if given polygon is a convex polygon or not Check whether two convex regular polygon have same center or not Minimum Enclosing Circle...

Frequently Asked Questions on Convex Hull:

Question 1: What is a convex hull?...